The Viterbi algorithm is a method for performing maximum likelihood sequence detection and can be used for decoding received data that has been generated via a convolutional code. Only a brief discussion of convolutional codes will be given here since they are well know in the art, however, full explanations can be found in many publications including “Digital Communications, 3rd Edition,” by J. G. Proakis, McGraw Hill, N.Y., 1995. Technical application details on Viterbi decoding can be found in publications such as “Viterbi decoding techniques in the TMS320C54x Family,” by in H. Hendrix, DSP Application Note: SPRA071, Texas Instruments, Inc., Dallas, Tex., June 1996.
A convolutional encoder is a finite state machine and the trellis diagram shown in FIG. 1 illustrates a single shift register code with 16 states of code rate 1/n. The state indices are shown in columns, each column or stage corresponds to an input bit to output bits mapping, and the branches are the possible transitions moving from left to right. During encoding, an input bit is allocated to each stage and it chooses between the two branches exiting each state, and each choice produces a small set of n output bits. Assuming the process is started in a known state (usually state zero), a given frame of input bits will generate a single unique path through the trellis.
A problem when performing Viterbi decoding is to determine the unique path that the input bits and initial state caused to be taken through the trellis by using the received data, which is an estimate of the transmitted output bits. Because of the noise and disturbances that occur in transmission, this received data will typically be a corrupted version of the encoder's output bits. So it is usually not possible to decode with absolute certainty. Instead, a typical approach is to determine the ‘most likely’ data sequence or path. This is done by finding the path through the trellis that has the minimum distance. The distances being defined by the sum of the branch metrics along the path. The branch metrics are determined from the received data and each one represents the likelihood of a particular choice of output bit values. Each branch has one branch metric (BM) and the number of BMs for a trellis stage equals the number of unique choices for output bits for a stage.
The Viterbi algorithm provides a very efficient method for finding this “most likely” path. The Viterbi algorithm operates in a step-wise manner by processing a set of state metrics (state metrics can also be called path metrics) forward in time, stage by stage over the trellis. At each step, or stage, each state metric is updated using the branch metrics, and in effect, the optimal path to that state is determined using the optimal paths to the previous stage's states. This is done by taking each state and selecting the optimal one-step path, or branch, of the two possibilities, from the previous stage. The optimal branch is the one that would give the smallest next state metric as defined by adding its branch metric to the state metric of the state from which the branch originates. This is known as the; add, compare and select operation (ACS). Each branch corresponds to a set of possible output bits and its metric is a distance measure from those output bits to the received data. Actually the bits are usually mapped to a constellation point that is transmitted and the metric is the Euclidean distance between the received data and this constellation point.
As the above process is performed, the chosen branches for each state at each stage are recorded, hence, the full optimal paths to each state are known. However, to produce the decoder's output, which will be the most likely match to the input bits above, we choose a state and walk backward through the stages following the path given by the recorded branches. If this process is started at the end of the frame, the chosen starting traceback state will be the encoder's known ending state; usually this is state zero. Output bits are then produced immediately.
If the traceback process starts prior to the end of a frame, any state can be chosen from which to start, though it is better to choose the state with the minimum state metric because better performance will be obtained. After a certain distance, known as the convergence distance, all the optimal paths from the other states will have converged to a single path with high probability. After that point valid output bits can be taken from the traceback process.
After the entire frame has been decoded, the Viterbi algorithm also provides the minimum path distance or full path metric through the trellis. It is obvious that this represents the likelihood of the correctness of the decoded sequence since it is the sum of likelihood measures along this “best” path. Thus, it can be very useful information for the receiver's data recovery process or for the end user.
When implementing a Viterbi algorithm, either in a specifically designed apparatus or as software on a small processor, some issues arise. One issue concerns minimizing versus maximizing with positive and negative branch metrics. In the standard theoretical derivation, the branch metrics are positive. However, in a very common set of design applications, the branch metric computation can be greatly simplified such that the branch metrics can become both positive and negative, and the algorithm still correctly identifies the most likely trellis path. It is also common to then remove a negative sign from the BM computation and to maximize the summed metrics instead of minimizing, as this is equivalent mathematically. For the most part, this scenario will be assumed in the rest of this application, although either approach can be utilized.
Another design issue concerns keeping the state metric values within the valid number range that their storage mechanism provides. This is necessary because usually there is a limited range provided by the assigned storage area and the state metrics continually grow in magnitude with each trellis stage. However, the state metrics have the property that the largest minus the smallest, at any trellis stage, will always be a bounded number that is a linear function of the encoder's memory length and the largest possible magnitude of the branch metrics. Thus, simple normalizations can be used.
Two common normalization methods used are subtractive scaling and modulo normalization. Subtractive scaling simply repeatedly subtracts a value from all state metrics to keep them within the desired range. Modulo normalization as for example described in, “An alternative to metric resealing in Viterbi decoders,” by A. P. Hekstra, IEEE Trans. Commun., vol. 37, no. 11, pp. 1220-1222, November 1989, simply constrains the arithmetic to occur in a modulo ring which is large enough such that the state metric differences can always be computed correctly. This is accomplished by simply making sure that the maximum possible difference in state metric values is less than ½ the size of the modulo ring. The modulo addition and subtraction can occur naturally in digital logic.
When modulo normalization is being used for the state metric updating process in a Viterbi decoder, critical information is lost such that the full decoding path metric cannot be obtained. This metric can have important uses within the larger system (e.g., cellular telephone, etc.) in which the decoder operates. A need thus exists in the art for a method of computing a full path metric when performing Veterbi decoding which can overcome some of the problems found in the prior art.